package leetcode.medium;

/**
 * Created by sheny on 2017/5/19.
 * 找到字符串中最长的回文子串
 */
public class LongestPalindromicSubstring_5 {
    public static void main(String[] args){
        System.out.println(longestPalindrome2
                ("rgczcpratwyqxaszbuwwcadruayhasynuxnakpmsyhxzlnxmdtsqqlmwnbxvmgvllafrpmlfuqpbhjddmhmbcgmlyeypkfpreddyencsdmgxysctpubvgeedhurvizgqxclhpfrvxggrowaynrtuwvvvwnqlowdihtrdzjffrgoeqivnprdnpvfjuhycpfydjcpfcnkpyujljiesmuxhtizzvwhvpqylvcirwqsmpptyhcqybstsfgjadicwzycswwmpluvzqdvnhkcofptqrzgjqtbvbdxylrylinspncrkxclykccbwridpqckstxdjawvziucrswpsfmisqiozworibeycuarcidbljslwbalcemgymnsxfziattdylrulwrybzztoxhevsdnvvljfzzrgcmagshucoalfiuapgzpqgjjgqsmcvtdsvehewrvtkeqwgmatqdpwlayjcxcavjmgpdyklrjcqvxjqbjucfubgmgpkfdxznkhcejscymuildfnuxwmuklntnyycdcscioimenaeohgpbcpogyifcsatfxeslstkjclauqmywacizyapxlgtcchlxkvygzeucwalhvhbwkvbceqajstxzzppcxoanhyfkgwaelsfdeeviqogjpresnoacegfeejyychabkhszcokdxpaqrprwfdahjqkfptwpeykgumyemgkccynxuvbdpjlrbgqtcqulxodurugofuwzudnhgxdrbbxtrvdnlodyhsifvyspejenpdckevzqrexplpcqtwtxlimfrsjumiygqeemhihcxyngsemcolrnlyhqlbqbcestadoxtrdvcgucntjnfavylip"));
    }
    public static int maxLength = 0;
    public static int start = 0;

    public static String longestPalindrome(String s) {
        char[] c = s.toCharArray();
        int length = -1;
        String result = "";
        for(int i=0;i<=c.length&&length<c.length-i;i++){
            for(int j=c.length-1;j>=0&&i<=j;j--){
                if(c[i] == c[j]){
                    String sub = s.substring(i,j+1);
                    StringBuilder re = new StringBuilder(sub);
                    if(re.reverse().toString().equals(sub) && length < sub.length()){
                        length = sub.length();
                        result = sub;
                        break;
                    }
                }
            }
        }
        return result;
    }

    public static String longestPalindrome2(String s) {
        int length = s.length();
        if(length <2){
            return s;
        }
        for(int i=0;i<length-1;i++){
            extend(s,i,i);
            extend(s,i,i+1);
        }
        return s.substring(start,start+maxLength);
    }
    public static void extend(String s,int i,int j){
        while (i>=0&&j<s.length()&&s.charAt(i) == s.charAt(j)){
            i--;
            j++;
        }
        if(maxLength < j-i-1){
            start = i+1;
            maxLength = j-i-1;
        }
    }
}
